The invention relates in general to the transmission of variable-rate bit streams and more particularly to the delivery of reference signal information in said bit streams within a specified time interval.
A new problem in data transmission is the transmission of data that requires a high bandwidth, is bursty, and has temporal constraints. Traditionally, data transmission has been done on the public switched networks provided by the telephone companies or on packet networks. The public switched networks are designed for interactive voice applications, and so provide relatively low-bandwidth circuits that satisfy stringent temporal constraints. The packet networks are designed for the transfer of data between computer systems. The only constraint is that the data eventually arrive at its destination. The amount of bandwidth available for a transfer depends on the degree of congestion in the network. The packet networks thus typically make no guarantees about when or even in what order the data in a burst of data will arrive at its destination.
It may thus be appreciated that neither the telephone network nor the packet network is well-adapted to handle high-bandwidth, bursty data with time constraints. An example of such data is digital television which has been compressed according to the Motion Picture Experts Group (xe2x80x9cMPEGxe2x80x9d) MPEG-2 standard, otherwise set forth in ISO/IEC 13818-1 and 13818-2.
Referring now to FIG. 1 there is illustrated therein those details of the MPEG-2 standard that enable one skilled in the art to understand the present invention. It is to be understood, however, that the instant invention as described hereinafter is not so limited, and will work with other data compression techniques. The MPEG-2 standard defines an encoding scheme for compressing digital representations of video. The encoding scheme takes advantage of the fact that video images generally have large amounts of spatial and temporal redundancy. There is spatial redundancy because a given video picture has sections where the entire area has the same appearance; the larger the areas and the more of them there are, the greater amount of spatial redundancy in the image. There is temporal redundancy because there is often not much change between a given video image and the ones that precede and follow it in a sequence. The less the amount of change between two video images, the greater the amount of temporal redundancy. The more spatial redundancy there is in an image and the more temporal redundancy there is in the sequence of images to which the image belongs, the fewer the bits of information that will be needed to represent the image.
Maximum advantage for the transmission of images encoded using the MPEG-2 standard is obtained if the images can be transmitted at variable bit rates. The bit rates can vary because the rate at which a receiving device receives images is constants while the images have a varying number of bits. A complex image therefore requires a higher bit rate than a simple image, and a sequence of MPEG images transmitted at variable bit rates is a variable-rate bit stream with time constraints. For example, a sequence of images that shows a news anchorperson in front of a solid color background will have much more spatial and temporal redundancy than a sequence of images for a commercial or MTV song presentation, and the bit rate for the images showing the news anchor will be far lower than the bit rate for the images of the MTV song presentation.
The MPEG-2 compression scheme presents a sequence of video images as a sequence of compressed pictures, each of which must be decoded at a specific time. There are three ways in which pictures may be compressed. One way is intra-coding, in which the compression is done without reference to any other picture. This encoding technique reduces spatial redundancy but not time redundancy, and the pictures resulting from it are generally larger than those in which the encoding reduces both spatial redundancy and temporal redundancy. Pictures encoded in this way are called I-pictures. A certain number of I-pictures are required in a sequence, first, because the initial picture of a sequence is necessarily an I-picture, and second, because I-pictures permit recovery from transmission errors.
Time redundancy is reduced by encoding pictures as a set of changes from earlier or later pictures or both. In MPEG-2, this is done using motion compensated forward and backward predictions. When a picture uses only forward motion compensated prediction, it is called a Predictive-coded picture, or P picture. When a picture uses both forward and backward motion compensated predictions, it is called a bi-directional predictive-coded picture, or a B picture in short. P pictures generally have fewer bits than I-pictures and B pictures have the smallest number of bits. The number of bits required to encode a given sequence of pictures in MPEG-2 is thus dependent on the distribution of picture coding types mentioned above, as well as the picture content itself As will be apparent from the foregoing discussion, the sequence of pictures required to encode the images of the news anchorperson will have fewer and smaller I-pictures and smaller B and P pictures than the sequence required for the MTV song presentation, and consequently, the MPEG-2 representation of the images of the news anchorperson will be much smaller than the MPEG-2 representation of the images of the MTV sequence.
The MPEG-2 pictures are being received by a low-cost consumer electronics device such as a digital television set or a set-top box provided by a cable television (xe2x80x9cCATVxe2x80x9d) service provider. The low cost of the device strictly limits the amount of memory available to store the MPEG-2 pictures. Moreover, the pictures are being used to produce moving images. The MPEG-2 pictures must consequently arrive in the receiver in the right order and with time intervals between them such that the next MPEG-2 picture is available when needed and there is room in the memory for the picture which is currently being sent. In the art, a memory which has run out of data is said to have underflowed, while a memory which has received more data than it can hold is said to have overflowed. In the case of underflow, the motion in the TV picture must stop until the next MPEG-2 picture arrives, and in the case of overflow, the data which did not fit into memory is simply lost.
FIG. 1 is a representation of a system 10 including digital picture source 12 and a television 14 that are connected by a channel 16 that is carrying a MPEG-2 bit stream representation of a sequence of TV images. The digital picture source 12 generates uncompressed digital representations (xe2x80x9cUDRxe2x80x9d) of images 18, which go to variable bit rate (xe2x80x9cVBRxe2x80x9d) encoder 20. Encoder 20 encodes the uncompressed digital representations to produce variable rate bit stream (xe2x80x9cVRBSxe2x80x9d) 22. Variable rate bit stream 22 is a sequence of compressed digital pictures 24 of variable length. As indicated above, when the encoding is done according to the MPEG-2 standard, the length of a picture depends on the complexity of the image it represents and whether it is an I-picture, a P picture, or a B picture. Additionally, the length of the picture depends on the encoding rate of VBR encoder 20. That rate can be varied. In general, the more bits used to encode a picture, the better the picture quality.
The variable rate bit stream 22 is transferred via channel 16 to VBR decoder 26, which decodes the compressed digital pictures 24 to produce uncompressed digital pictures 105. These in turn are provided to television 117. If television 117 is a digital television, they will be provided directly; otherwise, there will be another element which converts uncompressed digital pictures (xe2x80x9cUDPxe2x80x9d) 28 into standard analog television signals and then provides those signals to television 14. There may of course be any number of VBR decoders 26 receiving the output of a single encoder 20.
In FIG. 1, channel 16 transfers bit stream 22 as a sequence of packets 30. The compressed digital pictures 24 thus appear in FIG. 1 as varying-length sequences of packets 30. Thus, picture 24(a) may have xe2x80x9cnxe2x80x9d packets while picture 24(d) has xe2x80x9ckxe2x80x9d packets. Included in each picture 24 is timing information 32. Timing information contains two kinds of information: clock information and time stamps. Clock information is used to synchronize decoder 26 with encoder 20. The time stamps include the Decoding Time Stamp (xe2x80x9cDTSxe2x80x9d) which specifies when a picture is to be decoded and the Presentation Time Stamp (xe2x80x9cPTSxe2x80x9d) which specifies when the picture is actually to be displayed. The times specified in the time stamps are specified in terms of the clock information. As indicated above, VBR decoder 26 contains a relatively small amount of memory for storing pictures 30 until they are decoded and provided to TV 14. This memory is shown at 34 in FIG. 1 and will be referred to hereinafter as the decoder""s bit buffer. Bit buffer 34 must be at least large enough to hold the largest possible MPEG-2 picture. Further, channel 16 must provide the pictures 24 to bit buffer 34 in such fashion that decoder 26 can make them available at the proper times to TV 14 and that bit buffer 34 never overflows or underflows. Bit buffer 34 underflows if not all of the bits in a picture 24 have arrived in bit buffer by the time specified in the picture""s time stamp for decoder to begin decoding the picture.
Providing pictures 24 to VBR decoder 26 in the proper order and at the proper times is made more complicated by the fact that a number of channels 16 may share a single very high bandwidth data link. For example, a CATV provider may use a satellite link to provide a large number of TV programs from a central location to a number of CATV network head ends, from which they are transmitted via coaxial or fiber optic cable to individual subscribers or may even use the satellite link to provide the TV programs directly to the subscribers. When a number of channels share a medium such as a satellite link, the medium is said to be multiplexed among the channels.
FIG. 2 shows such a multiplexed medium. A number of channels 16(0) through 16(n) which are carrying packets containing bits from variable rate bit streams 22(0 . . . n) are received in multiplexer 40, which processes the packets as required to multiplex them onto high bandwidth (xe2x80x9cHBWxe2x80x9d) medium 42. The packets then go via medium 42 to demultiplexer 44, which separates the packets into the packet streams for the individual channels 16(0 . . . n). A simple way of sharing a high bandwidth medium among a number of channels that are carrying digital data is to repeatedly give each individual channel 16 access to the high bandwidth medium for a short period of time, referred to hereinafter as a slot.
One way of doing this is shown at 50 in FIG. 2. The short period of time appears at 50 as a slot 52; during a slot 52, a fixed number of packets 32 belonging to a channel 16 may be output to medium 42. Each channel 16 in turn has a slot 52, and all of the slots taken together make up a time slice 54. When medium 42 is carrying channels like channel 16 that have varying bit rates and time constraints, slot 52 for each of the channels 16 must output enough packets to provide bits at the rate necessary to send the largest pictures to channel 16 within channel 16""s time, overflow, and underflow constraints. Of course, most of the time, a channel""s slot 52 will be outputting fewer packets than the maximum to medium 42, and sometimes may not be carrying any packets at all. Since each slot 52 represents a fixed portion of medium 42""s total bandwidth, any time a slot 52 is not full, a part of medium 42""s bandwidth is being wasted.
In order to avoid wasting the medium bandwidth, a technique is used which ensures that each time slice is generally almost full of packets. This technique is termed statistical multiplexing. It takes advantage of the fact that at a given moment in time, each of the channels in a set of channels will be carrying bits at a different bit rate, and the medium bandwidth need only be large enough at that moment of time to transmit what the channels are presently carrying, not large enough to transmit what all of the channels could carry if they were transmitting at the maximum rate. The output of the channels is analyzed statistically to determine what the actual maximum rate of output for the entire set of channels will be and the medium bandwidth is sized to satisfy that actual peak rate. Typically, the bandwidth that is determined in this fashion will be far less than is required for multiplexing in the manner shown at 50 in FIG. 2. As a result, more channels can be sent in a given amount of bandwidth. At the level of slots, what statistical multiplexing requires is a mechanism which in effect permits a channel to have a slot in time slice 54 which varies in length to suit the actual needs of channel 16 during that time slice 54. Such a time slice 54 with varying-length slots 56 is shown at 55.
Methods of statistically multiplexing bit streams are disclosed in, for example, U.S. Pat. No. 5,506,844, entitled, Method for Configuring a Statistical Multiplexer to Dynamically Allocate Communication Channel Bandwidth, to Rao, issued Apr. 9, 1996; and U.S. patent application Ser. No. 08/823,007 entitled Using a Receiver Model to Multiplex Variable Rate Bit Streams Having Timing Constraints, filed Mar. 21, 1997, the disclosures of each of which are incorporated herein by reference.
Unlike the variable bit rate (xe2x80x9cVBRxe2x80x9d) multiplexers described herein above, prior art multiplexers encoded information at a constant bit rate (xe2x80x9cCBRxe2x80x9d). By constant bit rate it is meant that the same number of bits of information were encoded and output per each similar time unit. Conversely in VBR, more or less bits of information may be encoded and transmitted per unit of time. Accordingly, program clock reference information (xe2x80x9cPCRxe2x80x9d) necessary to assure that both the encoder and decoder are synchronized for proper decoding and presentation of video information could be, under a CBR format, transmitted at regular intervals. These regular intervals allow the decoder to look for PCR information in the bit stream in a timely manner. For example, the time interval specified by the Digital Video Broadcast (DVB) standard, as well as others, is typically on the order of approximately 40 milliseconds.
However, when the MPEG/DVB compliant bit stream goes through the statistical multiplexing operation in the method disclosed in the patent application entitled xe2x80x9cUsing a Receiver Model to Multiplex Variable-Rate Bit Streams Having Timing Constraints,xe2x80x9d the bit delivery time schedule is changed due to the buffering mechanism and also due to the inter-channel multiplexing process. This results in PCR interval variation from the original input bit stream. When packets are delivered faster than the speed it arrives at the buffer, the PCR interval is squeezed, i.e., shortened. When packets are delivered slower than the speed at which it arrives at the buffer, the PCR interval is stretched, i.e., lengthened. The later case will generate a muxed output bit stream that would violate the MPEG/DVB specifications on the PCR time interval, which will result in lost or erroneous video information.
Accordingly, there exists a need for a method and apparatus which will assure delivery of PCR information within the time interval threshold required standards currently employed. The method and apparatus must take into account that the bit streams may be output at variable rates, and hence PCR information packets while being generated at uniform time intervals, are not necessarily transmitted or output to decoders in uniform time intervals. Accordingly, the method and apparatus must assure that some PCR information is transmitted or output to decoders at intervals which are less than the time interval threshold required for the standard.